package leetcode_zh

import (
	"sort"
	"strconv"
	"strings"
)

/**
 * @Description: 93. 复原 IP 地址 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/31 20:19
 **/
func restoreIpAddresses(s string) []string {
	res := []string{}
	var dfs func(subRes []string, start int)

	dfs = func(subRes []string, start int) {
		if len(subRes) == 4 && start == len(s) {
			res = append(res, strings.Join(subRes, "."))
			return
		}
		if len(subRes) == 4 && start < len(s) {
			return
		}
		for length := 1; length <= 3; length++ {
			// 超过最后字符
			if start+length-1 >= len(s) {
				return
			}
			//如果是 01/02/03...跳过
			if length != 1 && s[start] == '0' {
				return
			}
			// 形成选项
			str := s[start : start+length]
			if n, _ := strconv.Atoi(str); n > 255 {
				return
			}
			// 加入当前结果
			subRes = append(subRes, str)
			// 递归
			dfs(subRes, start+length)
			// 撤销当前选择
			subRes = subRes[:len(subRes)-1]
		}
	}

	dfs([]string{}, 0)

	return res
}

/**
 * @Description: 1143. 最长公共子序列 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/1 13:48
 **/
func longestCommonSubsequence(text1 string, text2 string) int {
	var m = len(text1)
	var n = len(text2)
	var dp = make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		dp[i] = make([]int, n+1)
	}
	// dp[i][j] 代表i字符和j字符的公共最长子串
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				continue
			}
			dp[i][j] = getMax(dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[m][n]
}

/**
 * @Description: 剑指 Offer II 119. 最长连续序列 中等
 * @Keyword: 排序
 * @Author: kami
 * @Date: 2022/6/1 14:59
 **/
func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	var max = 1
	var cnt = 1
	for i := 1; i < len(nums); i++ {
		var diff = nums[i] - nums[i-1]
		if diff == 1 {
			cnt += 1
			max = getMax(max, cnt)
		} else if diff == 0 {
			continue
		} else {
			cnt = 1
		}
	}
	return max
}

/**
 * @Description: 剑指 Offer II 095. 最长公共子序列 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/1 15:28
 **/
func longestCommonSubsequence95(text1 string, text2 string) int {
	m := len(text1)
	n := len(text2)
	var dp = make([][]int, m+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, m+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				continue
			}
			dp[i][j] = getMax(dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[m][n]
}

/**
 * @Description: 128. 最长连续序列 中等
 * @Keyword: O(n) 时间复杂度
 * @Author: kami
 * @Date: 2022/6/1 15:34
 **/
func longestConsecutive128(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var numMap = make(map[int]bool, len(nums))
	for i := 0; i < len(nums); i++ {
		numMap[nums[i]] = true
	}
	var max = 1
	for i := 0; i < len(nums); i++ {
		if _, ok := numMap[nums[i]-1]; ok {
			var cnt = 1
			var val = nums[i] - 1
			for numMap[val] {
				cnt++
				delete(numMap, val)
				val -= 1
			}
			val = nums[i] + 1
			for numMap[val] {
				cnt++
				delete(numMap, val)
				val += 1
			}
			max = getMax(max, cnt)
		}
	}

	return max
}

/**
 * @Description:剑指 Offer 48. 最长不含重复字符的子字符串 中等
 * @Keyword: 子串不是子序列，得是连续的
 * @Author: kami
 * @Date: 2022/6/1 16:13
 **/
func lengthOfLongestSubstring48(s string) int {
	var n = len(s)
	if n == 0 {
		return 0
	}
	var max = 1
	for i := 0; i < n-1; {
		var idx = i
		var curMap = make(map[byte]int)
		for idx < n && curMap[s[idx]] == 0 {
			curMap[s[idx]] = idx
			idx++
		}
		var size = idx - i
		if size > max {
			max = size
		}
		i = curMap[s[idx]] + 1
	}
	return max
}

/**
 * @Description: 647. 回文子串 中等
 * @Keyword: 有轴对称，无轴对称
 * @Author: kami
 * @Date: 2022/6/11 16:33
 **/
func countSubstrings(s string) int {
	var size = len(s)
	var cnt = size
	var maxIdx = size - 1
	for i := 0; i < size; i++ {
		// 有轴对称
		var left = i - 1
		var right = i + 1
		for left >= 0 && right <= maxIdx && s[left] == s[right] {
			left--
			right++
			cnt++
		}
		// 无轴对称
		var low = i
		var high = i + 1
		for low >= 0 && high <= maxIdx && s[low] == s[high] {
			low--
			high++
			cnt++
		}
	}
	return cnt
}
